package com.huawei.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author admin
 * @Description 不同的二叉搜索树：左边的节点值 < 中间的节点值 < 右边的节点值
 * @Date 2023/11/12/9:46
 * @Version 1.0
 */
public class DifferentBinarySearchTrees {
	public static Map<Integer, Integer> map = new HashMap<>();

	public static void main(String[] args) {
		DifferentBinarySearchTrees differentBinarySearchTrees = new DifferentBinarySearchTrees();
		System.out.println(differentBinarySearchTrees.numTrees(3));
	}

	/**
	 * 解题思路：
	 * 1、对于数组中每个元素来说都有可能是根节点root,
	 * 2、其左边有四个节点，右边有两个节点。对于左边的四个节点，假设能延伸出 n 种二叉搜索树子树，
	 * 3、对于右边的两个节点，假设能延伸出 m 种二叉搜索树子树。则以5为root节点时的二叉搜索树总数为 m*n
	 * 递归套路 3步走：
	 * (1) 函数作用、参数意义及其返回值：
	 *     - 函数作用：该函数的意义可以由原本的意义，n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树的方案总数，
	 *               转变为n个节点组成的互不相同的二叉搜索树的方案总数；
	 *     - 参数意义：n，即节点总数。
	 *     - 返回值：即方案总数。
	 * (2) base case：即递归出口，当n==1||n==2时，显而易见答案就是n。
	 * (3) 单层递归的逻辑：
	 *     - 当n>2时，假设当前的根节点root->val=i，在此基础上分别计算val＜root->val的节点个数和val>root->val的节点个数（即左子树和右子树的节点个数）
	 *     - 然后由左子树的方案总数*右子树的方案总数即可得到由该节点组成root构成的二叉搜索树的方案总数，枚举每一个节点当root的方案即可。
	 * @param n int
	 * @return int
	 */
	public int numTrees(int n) {
		// 如果只有0，或者1个节点，则可能的子树情况为1种
		if (n == 0 || n == 1) {
			return 1;
		}
		if (map.containsKey(n)) {
			return map.get(n);
		}
		int count = 0;
		for (int i = 1; i <= n; i++) {
			// 当用i这个节点当做根节点时
			// 左边有多少种子树
			int leftNum = numTrees(i - 1);
			// 右边有多少种子树
			int rightNum = numTrees(n - i);
			// 乘起来就是当前节点的子树个数
			count += leftNum * rightNum;
		}
		map.put(n, count);
		return count;
	}


}
